package 集合.stack;

import java.util.Deque;
import java.util.ArrayDeque;
//import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

//import java.util.Map;
//import java.util.Stack;
public class 后缀表达式 {
	public static void main(String[] args) {
		String str = "(10+20/2*3)/(2+8)";
		String result = infixToSuffix(str);
		System.out.println(result);
	}

	static String infixToSuffix(String infixExpression) {
		// 定义一个操作符栈
		Deque<String> opStack = new ArrayDeque<>();
		// 定义一个存后缀字符的线性表
		ArrayList<String> suffixList = new ArrayList<>();

		// 格式化表达式
		infixExpression = insertBlanks(infixExpression);// 在符号两侧加一空格，数字则不加
		String[] tokens = infixExpression.split(" ");// 以一空格作为分隔符，将infixExpression转换成字符串数组
		System.out.println(Arrays.toString(tokens));

		for (String token : tokens) {
			if (token.length() == 0) {
				continue;
			}
			if (isOperator(token)) { // 如果是操作符，即非数字的：+ - * / ( )
				while (true) {
					// 栈空 或 栈顶是( 直接进; 当前操作符的优先级 > 栈顶操作符的优先级 直接进
					if (opStack.isEmpty() || "(".equals(opStack.peek()) || priority(token) > priority(opStack.peek())) {
						opStack.push(token);
						break;
					}
					// 如果栈不为空 且 栈顶不是( 且栈顶操作符优先级 >= 当前操作符优先级，将opStack栈顶操作符弹出压入suffixList，然后继续比较
					suffixList.add(opStack.pop());
				}
			} else if (isNumber(token)) { // 如果是数字
				suffixList.add(token);
			} else if ("(".equals(token)) { // 如果是“(”
				opStack.push(token);
			} else if (")".equals(token)) { // 如果是“)”
				while (true) {
					if ("(".equals(opStack.peek())) {
						opStack.pop();
						break;
					} else {
						suffixList.add(opStack.pop());
					}
				}
			} else {
				throw new IllegalArgumentException("wrong identify" + token);
			}
		}
		while (!opStack.isEmpty()) {
			suffixList.add(opStack.pop());
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < suffixList.size(); i++) {
			sb.append(suffixList.get(i) + " ");
		}
		return sb.toString();
	}

	static int priority(String token) {
		if ("*".equals(token) || "/".equals(token)) {
			return 1;
		} else if ("+".equals(token) || "-".equals(token)) {
			return 0;
		} else {
			return -1;// （ ）返回-1
		}
	}

	static boolean isOperator(String token) {
		return "+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token);
	}

	static boolean isNumber(String token) {
		return token.matches("\\d+"); // \\d+匹配的是表示多个数字
	}

	static String insertBlanks(String expression) {
		StringBuilder sb = new StringBuilder();
		// 遍历表达式
		for (int i = 0; i < expression.length(); i++) {
			char c = expression.charAt(i);
			// 如果是符号，则在符号前后增加空格
			if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {
				sb.append(" ");
				sb.append(c);
				sb.append(" ");
			} else { // 如果遇到数字 则原封不动添加在sb
				sb.append(c);
			}
		}
		return sb.toString();
	}
}